package 力扣_链表.简单;

/**
 * @author zx
 * @create 2022-08-15 17:27
 */
public class 回文链表_234 {
    public boolean isPalindrome(ListNode head) {
        //回文链表 = 中间节点 + 反转链表
        //找到链表的中间节点
        ListNode midNode = midNode(head);
        ListNode reverse = reverseList(midNode);
        midNode.next = null;
        ListNode temp = reverse;
        while(temp != null){
            if(head.val != temp.val){
                return false;
            }
            temp = temp.next;
            head = head.next;
        }
        return true;
    }
    public ListNode reverseList(ListNode head){//206题：反转链表
        //原地移动法
        if(head == null && head.next == null){
            return head;
        }
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
    public ListNode midNode(ListNode head){//876题：链表的中间节点
        ListNode fast = head;
        ListNode low = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
        }
        return low;
    }
}
